package day01;

/**
 * @author Jetwang
 * @version 1.0
 * @since 2023/2/24 20:17
 * 二分查找
 */
public class BinarySearch {
    public static void main(String[] args) {
        // 前提: 数组必须有序!
        int[] arr = { 1, 2, 4, 6, 8, 10 };
        int index = binarySearch(arr, 6);
        System.out.println(index);
    }

    private static int binarySearch(int[] arr, int target) {
        int start = 0, end = arr.length - 1;
        // 条件是 start <= end 而不是 start < end 有可能重叠的地方就是目标值，否则可能漏掉比较
        while (start <= end) {
            // 可以直接使用(start + end) / 2吗??
            // 有可能造成溢出 当 start + end 大于int的范围时!
            // 可以改写成 start + (end - start) / 2
            // int middle = (start + end) / 2;
            // 或者采用无符号右移运算符 (start + end) >>> 1
            // int middle = start + (end - start) / 2;
            int middle = (start + end) >>> 1;
            if (arr[middle] == target) {
                return middle;
            } else if (arr[middle] < target) {
                start = middle + 1;
            } else {
                end = middle - 1;
            }
        }
        return -1;
    }
}
